package com.fw.leetcode.greedy;

import com.fw.leetcode.Index;
import com.fw.leetcode.LeetCode;

/**
 * 410. Split Array Largest Sum
 * 分割数组最大和最小化
 *
 * Given an integer array nums and an integer k,
 * split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.
 *
 * Return the minimized largest sum of the split.
 *
 * A subarray is a contiguous part of the array.
 *
 * Example 1:
 *  Input: nums = [7,2,5,10,8], k = 2
 *  Output: 18
 *  Explanation: There are four ways to split nums into two subarrays.
 *  The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
 *
 * Example 2:
 *  Input: nums = [1,2,3,4,5], k = 2
 *  Output: 9
 *  Explanation: There are four ways to split nums into two subarrays.
 *  The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
 *
 * Constraints:
 *  1 <= nums.length <= 1000
 *  0 <= nums[i] <= 10^6
 *  1 <= k <= min(50, nums.length)
 */
public class Num_0410 implements LeetCode {

    private interface Solution {
        int splitArray(int[] nums, int k);

        default void assertExpected(int[] nums, int k, int expected) {
            if (splitArray(nums, k) != expected) {
                splitArray(nums, k);
            }
        }
    }

    private static class DpSuffixSolution implements Solution {

        @Override
        public int splitArray(int[] nums, int k) { // 动态规划（后缀分割）：时O(n^2×m) 空O(nm)
            /*
             * 所谓分割子数组，就是不能打乱顺序，在原数组基础上切分，k >= 2
             *
             * nums = [7,2,5,10,8], k = 2
             * => [7,2,5] and [10,8]
             *
             * 后半部分的k-1分割，前半部分作为不分割
             *   f(k)[0,n-1] = min(j=0~n-2) { max { f(1)[0,  j], f(k-1)[j+1, n-1] } }
             *   f(3)[0,n-1] = min(j=0~n-2) { max { f(1)[0,  j], f(2  )[j+1, n-1] } }
             *   f(2)[0,n-1] = min(j=0~n-2) { max { f(1)[0,  j], f(1  )[j+1, n-1] } }
             *   f(1)[0,n-1] = min(j=0~n-1) { max { f(1)[0,  j], f(0  )[j+1, n-1] } }
             *
             * 将上述第一式中 0 替换成 i，以适配 f(k-1)[j+1, n-1] 使其形式与 f(k)[0,n-1] 一致
             *   即得正确形式1：
             *   f(k)[i,n-1] = (i=0<-n-k) min(j=i<-n-k) { max { f(1)[i,j], f(k-1)[j+1, n-1] } }
             *               .
             *   f(3)[i,n-1] = (i=0<-n-3) min(j=i<-n-3) { max { f(1)[i,j], f(2)[j+1, n-1] } }
             *   f(2)[i,n-1] = (i=0<-n-2) min(j=i<-n-2) { max { f(1)[i,j], f(1)[j+1, n-1] } }
             *   f(1)[i,n-1] = sum([i,n-1]) <= 起点，向上迭代，因 k=1 时不分割
             *
             *   解释：
             *   - f(k)[i,n-1] 是在区间 [i,n-1] 上划分 k 次，取不同 j 作为划分点的结果集中最小的值
             *   - f(1)[i,j] = sum([i,n-1]) - sum([j+1,n-1]) = sum(i) - sum(j+1)
             *   - - - 例如：从后向前加，末位是辅助计数位
             *   - - - [1,2,3,4] => sum [10,9,7,4,0]
             *   - - - 求 f(1)[1,2] = sum([1,4-1])-sum([2+1,4-1]) = sum(1) - sum(3) = 5
             *
             * 错误形式：
             *   f(k)[0,i] = min(j=0~i-1) { max { f(1)[0,j], f(k-1)[j+1, i] } } => 问题：f(k-1)[j+1, i] 无法与 f(k)[0,i] 匹配
             */
            // 形式1 实现
            int n = nums.length;
            int[][] dpf = new int[k+1][n+1]; // 第0行弃用
            // 1.首次计算 k=1 时，即不分组的情况，从后向前依次累加计算后 i 个元素的和
            for (int i = n-1; i >= 0; i--) {
                dpf[1][i] = dpf[1][i+1] + nums[i];
            }
            // 2.遍历迭代更高的 k>1 情况
            for (int tmpK = 2; tmpK <= k; tmpK++) {
                // 当前 k 时，从后向前依次累加计算最大值
                for (int i = n-tmpK; i >= 0; i--) {
                    dpf[tmpK][i] = Integer.MAX_VALUE;
                    for (int j = n-tmpK; j >= i; j--) {
                        dpf[tmpK][i] = Math.min(
                                dpf[tmpK][i],
                                Math.max(dpf[1][i] - dpf[1][j+1], dpf[tmpK-1][j+1])
                        );
                    }
                }
            }

            return dpf[k][0];
        }
    }

    private static class DpPrefixSolution implements Solution {

        @Override
        public int splitArray(int[] nums, int k) { // 动态规划（前缀分割）：时O(n^2×m) 空O(nm)
            /*
             * 所谓分割子数组，就是不能打乱顺序，在原数组基础上切分，k >= 2
             *
             * nums = [7,2,5,10,8], k = 2
             * => [7,2,5] and [10,8]
             *
             * 前半部分的k-1分割，后半部分作为不分割
             *   f(k)[0,n-1] = min(j=0~n-k) { max { f(k-1)[0,j], f(1)[j+1, n-1] } }
             *   f(3)[0,n-1] = min(j=0~n-3) { max { f(2  )[0,j], f(1)[j+1, n-1] } }
             *   f(2)[0,n-1] = min(j=0~n-2) { max { f(1  )[0,j], f(1)[j+1, n-1] } }
             *   f(1)[0,n-1] = min(j=0~n-1) { max { f(0  )[0,j], f(1)[j+1, n-1] } }
             *
             * 将上述第一式中 n-1 替换成 i，以适配 f(k-1)[0, j] 使其形式与 f(k)[0,n-1] 一致
             *   即得正确形式2：
             *   f(k)[0,i] = (i=k-1->n-1) min(j=k-2->i-1) { max { f(k-1)[0,j], f(1)[j+1, i] } }
             *             .
             *   f(3)[0,i] = (i=2->n-1) min(j=1->i-1) { max { f(2)[0,j], f(1)[j+1, i] } }
             *   f(2)[0,i] = (i=1->n-1) min(j=0->i-1) { max { f(1)[0,j], f(1)[j+1, i] } }
             *   f(1)[0,i] = sum([0,i]) <= 起点，向上迭代，因 k=1 时不分割
             *
             *   解释：
             *   - f(k)[0,i] 是在区间 [0,i] 上划分 k 次，取不同 j 作为划分点的结果集中最小的值
             *   - f(1)[j+1, i] = sum([0,i]) - sum([0,j]) = sum(i) - sum(j)
             *   - - - 例如：从前向后加，首位是辅助计数位
             *   - - - [1,2,3,4] => sum [1,3,6,10]
             *   - - - 求 f(1)[1,2] = sum([0,2])-sum([0,0]) = sum(2) - sum(0) = 5
             */
            // 形式2 实现
            int n = nums.length;
            int[][] dpf = new int[k+1][n]; // 第0行弃用
            // 1.首次计算 k=1 时，即不分组的情况，从前向后依次累加计算后 i 个元素的和
            dpf[1][0] = nums[0];
            for (int i = 1; i < n; i++) {
                dpf[1][i] = dpf[1][i-1] + nums[i]; // 依然要满足 dpf[k][i] 语义
            }
            // 2.遍历迭代更高的 k>1 情况
            for (int tmpK = 2; tmpK <= k; tmpK++) {
                // 当前 k 时，从前向后依次累加计算最大值
                for (int i = tmpK-1; i <= n-1; i++) {
                    dpf[tmpK][i] = Integer.MAX_VALUE;
                    for (int j = tmpK-2; j <= i-1; j++) {
                        dpf[tmpK][i] = Math.min(
                                dpf[tmpK][i],
                                Math.max(
                                        dpf[tmpK-1][j] // 要与 k-1 层次上的 j 位置对应
                                        ,dpf[1][i] - dpf[1][j]
                                )
                        );
                    }
                }
            }

            return dpf[k][n-1];
        }
    }

    public static void main(String[] args) {
        Solution solution = new DpPrefixSolution();
        solution.assertExpected(new int[]{7, 2, 5, 10, 8}, 2, 18);
        solution.assertExpected(new int[]{1, 4, 4}, 3, 4);
        solution.assertExpected(new int[]{1, 2, 3, 4, 5}, 2, 9);
    }
}
